{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Genetic Difference Query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxGeneticDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询最大基因差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <code>n</code> 个节点的有根树，节点编号从 <code>0</code> 到 <code>n - 1</code> 。每个节点的编号表示这个节点的 <strong>独一无二的基因值</strong> （也就是说节点 <code>x</code> 的基因值为 <code>x</code>）。两个基因值的 <strong>基因差</strong> 是两者的 <strong>异或和</strong> 。给你整数数组 <code>parents</code> ，其中 <code>parents[i]</code> 是节点 <code>i</code> 的父节点。如果节点 <code>x</code> 是树的 <strong>根</strong> ，那么 <code>parents[x] == -1</code> 。</p>\n",
    "\n",
    "<p>给你查询数组 <code>queries</code> ，其中 <code>queries[i] = [node<sub>i</sub>, val<sub>i</sub>]</code> 。对于查询 <code>i</code> ，请你找到 <code>val<sub>i</sub></code> 和 <code>p<sub>i</sub></code> 的 <strong>最大基因差</strong> ，其中 <code>p<sub>i</sub></code> 是节点 <code>node<sub>i</sub></code> 到根之间的任意节点（包含 <code>node<sub>i</sub></code> 和根节点）。更正式的，你想要最大化 <code>val<sub>i</sub> XOR p<sub>i</sub></code><sub> </sub>。</p>\n",
    "\n",
    "<p>请你返回数组<em> </em><code>ans</code> ，其中 <code>ans[i]</code> 是第 <code>i</code> 个查询的答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/29/c1.png\" style=\"width: 118px; height: 163px;\">\n",
    "<pre><b>输入：</b>parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]\n",
    "<b>输出：</b>[2,3,7]\n",
    "<strong>解释：</strong>查询数组处理如下：\n",
    "- [0,2]：最大基因差的对应节点为 0 ，基因差为 2 XOR 0 = 2 。\n",
    "- [3,2]：最大基因差的对应节点为 1 ，基因差为 2 XOR 1 = 3 。\n",
    "- [2,5]：最大基因差的对应节点为 2 ，基因差为 5 XOR 2 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/29/c2.png\" style=\"width: 256px; height: 221px;\">\n",
    "<pre><b>输入：</b>parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]\n",
    "<b>输出：</b>[6,14,7]\n",
    "<strong>解释：</strong>查询数组处理如下：\n",
    "- [4,6]：最大基因差的对应节点为 0 ，基因差为 6 XOR 0 = 6 。\n",
    "- [1,15]：最大基因差的对应节点为 1 ，基因差为 15 XOR 1 = 14 。\n",
    "- [0,5]：最大基因差的对应节点为 2 ，基因差为 5 XOR 2 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= parents.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>对于每个 <strong>不是</strong> 根节点的 <code>i</code> ，有 <code>0 &lt;= parents[i] &lt;= parents.length - 1</code> 。</li>\n",
    "\t<li><code>parents[root] == -1</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= node<sub>i</sub> &lt;= parents.length - 1</code></li>\n",
    "\t<li><code>0 &lt;= val<sub>i</sub> &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-genetic-difference-query](https://leetcode.cn/problems/maximum-genetic-difference-query/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-genetic-difference-query](https://leetcode.cn/problems/maximum-genetic-difference-query/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,1,1]\\n[[0,2],[3,2],[2,5]]', '[3,7,-1,2,0,7,0,2]\\n[[4,6],[1,15],[0,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = ['son',\"cnt\"]\n",
    " \n",
    "    def __init__(self):\n",
    "        self.son = [None, None]\n",
    "        self.cnt = 0\n",
    "    def add(self,x):\n",
    "        node=self\n",
    "        for i in range(19,-1,-1):\n",
    "            c=x>>i&1\n",
    "            if node.son[c] is None:\n",
    "                node.son[c]=Trie()\n",
    "            node=node.son[c]\n",
    "            node.cnt+=1\n",
    "    def remove(self,x):\n",
    "        node=self\n",
    "        for i in range(19,-1,-1):\n",
    "            c=x>>i&1\n",
    "            node=node.son[c]\n",
    "            node.cnt-=1\n",
    "    \n",
    "    def query(self,x):\n",
    "        res=0\n",
    "        node=self\n",
    "        for i in range(19,-1,-1):\n",
    "            c=x>>i&1\n",
    "            if node.son[c^1] and node.son[c^1].cnt>0:\n",
    "                res+=1<<i\n",
    "                node=node.son[c^1]\n",
    "            else:\n",
    "                node=node.son[c]\n",
    "        return res\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(parents)\n",
    "        root=-1\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i,p in enumerate(parents):\n",
    "            if p==-1:\n",
    "                root=i\n",
    "            else:\n",
    "                g[p].append(i)\n",
    "        q=len(queries)\n",
    "        res=[0]*q\n",
    "        query=[[] for _ in range(n)]\n",
    "        for i in range(q):\n",
    "            node,val=queries[i]\n",
    "            query[node].append([i,val])\n",
    "        trie=Trie()\n",
    "        def dfs(u):\n",
    "            trie.add(u)\n",
    "            for i,v in query[u]:\n",
    "                res[i]=trie.query(v)\n",
    "            for v in g[u]:\n",
    "                dfs(v)\n",
    "            trie.remove(u)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "HIGH_BIT = 18   # 给定数据范围的最高二进制位数\n",
    "class Trie:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 2\n",
    "        # 经过当前节点的数的数量\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, x):\n",
    "        '''将数字 x 按照二进制位从高到低的顺序插入到字典树中'''\n",
    "        node = self\n",
    "        for i in range(HIGH_BIT, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            if node.children[v] is None:\n",
    "                node.children[v] = Trie()\n",
    "            node = node.children[v]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def delete(self, x):\n",
    "        '''删去一个数字 x'''\n",
    "        node = self\n",
    "        for i in range(HIGH_BIT, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            node = node.children[v]\n",
    "            node.cnt -= 1\n",
    "\n",
    "    def searchXorMax(self, x):\n",
    "        '''查找字典树中的数与 x 异或后最大值'''\n",
    "        node = self\n",
    "        res = 0\n",
    "        for i in range(HIGH_BIT, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            re = v ^ 1\n",
    "            if node.children[re] and node.children[re].cnt > 0:\n",
    "                node = node.children[re]\n",
    "                res |= 1 << i\n",
    "            else:\n",
    "                node = node.children[v]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                root = i\n",
    "\n",
    "        t = Trie()\n",
    "        dic = defaultdict(list)\n",
    "        for i, (q, v) in enumerate(queries):\n",
    "            dic[q].append((i, v))\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(node):\n",
    "            t.insert(node)\n",
    "            for i, v in dic[node]:\n",
    "                ans[i] = t.searchXorMax(v)\n",
    "            for ch in g[node]:\n",
    "                dfs(ch)\n",
    "            t.delete(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0  # 子树大小\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 20\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 添加 val\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 删除 val，但不删除节点\n",
    "    # 要求 val 必须在 trie 中\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            cur = cur.children[(val >> i) & 1]\n",
    "            cur.cnt -= 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 返回 val 与 trie 中一个元素的最大异或和\n",
    "    # 要求 trie 中至少有一个元素\n",
    "    def max_xor(self, val: int) -> int:\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            # 如果 cur.children[bit^1].cnt == 0，视作空节点\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 这个问题还是求两个异或的最大值\n",
    "        # 其次这个问题使一个查询问题，所以显然涉及离线查询的思路\n",
    "        # 可以用dfs + 0-1树处理完这个问题，只是涉及到增加删除异或操作\n",
    "\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(x)\n",
    "            else:\n",
    "                root = x\n",
    "        \n",
    "        qs = defaultdict(list)\n",
    "        for q, v in queries:\n",
    "            qs[q].append(v)\n",
    "        m = defaultdict(int)\n",
    "\n",
    "        def dfs(x, fa, tree):\n",
    "            tree.insert(x)\n",
    "            for v in qs[x]:\n",
    "                m[(x, v)] = tree.max_xor(v)\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x, tree)\n",
    "            tree.remove(x)\n",
    "\n",
    "        tree = Trie()\n",
    "        dfs(root, -1, tree)\n",
    "        \n",
    "        return [m[(x, q)] for x, q in queries]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "\n",
    "    __slots__ = {'count', 'children'}\n",
    "\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        self.children = [None, None]\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    __slots__ = {'root', 'MAX_BIT'}\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "        self.MAX_BIT = 20\n",
    "\n",
    "    def insert(self, num):\n",
    "        node = self.root\n",
    "        for bit in range(self.MAX_BIT, -1, -1):\n",
    "            bitVal = (num >> bit) & 1\n",
    "            if node.children[bitVal] is None:\n",
    "                node.children[bitVal] = TrieNode()\n",
    "            node = node.children[bitVal]\n",
    "            node.count += 1\n",
    "\n",
    "    def delete(self, num):\n",
    "        node = self.root\n",
    "        for bit in range(self.MAX_BIT, -1, -1):\n",
    "            bitVal = (num >> bit) & 1\n",
    "            if node.children[bitVal] is None:\n",
    "                return  # element does not exist\n",
    "            node = node.children[bitVal]\n",
    "            node.count -= 1\n",
    "\n",
    "    def maxXor(self, num):\n",
    "        node = self.root\n",
    "        max_xor = 0\n",
    "        for bit in range(self.MAX_BIT, -1, -1):\n",
    "            bitVal = (num >> bit) & 1\n",
    "            if node.children[1 - bitVal] and node.children[1 - bitVal].count > 0:\n",
    "                max_xor |= (1 << bit)\n",
    "                node = node.children[1 - bitVal]\n",
    "            else:\n",
    "                node = node.children[bitVal]\n",
    "        return max_xor\n",
    "\n",
    "    def minXor(self, num):\n",
    "        node = self.root\n",
    "        min_xor = 0\n",
    "        for bit in range(self.MAX_BIT, -1, -1):\n",
    "            bitVal = (num >> bit) & 1\n",
    "            if node.children[bitVal] and node.children[bitVal].count > 0:\n",
    "                node = node.children[bitVal]\n",
    "            else:\n",
    "                min_xor |= (1 << bit)\n",
    "                node = node.children[1 - bitVal]\n",
    "        return min_xor\n",
    "    \n",
    "    def countXorLessThan(self, num, limit):\n",
    "        node = self.root\n",
    "        count = 0\n",
    "        for bit in range(self.MAX_BIT, -1, -1):\n",
    "            bitVal = (num >> bit) & 1\n",
    "            limitBit = (limit >> bit) & 1\n",
    "            if limitBit:\n",
    "                if node.children[bitVal] is not None:\n",
    "                    count += node.children[bitVal].count\n",
    "                if node.children[1 - bitVal] is not None:\n",
    "                    node = node.children[1 - bitVal]\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                if node.children[bitVal] is not None:\n",
    "                    node = node.children[bitVal]\n",
    "                else:\n",
    "                    break\n",
    "        return count\n",
    "    \n",
    "    def countXorLessThanEqual(self, num, limit):\n",
    "        return self.countXorLessThan(num, limit + 1)\n",
    "\n",
    "    def countXorGreaterThan(self, num, limit):\n",
    "        total = sum(c.count for c in self.root.children if c is not None)\n",
    "        return total - self.countXorLessThanEqual(num, limit)\n",
    "\n",
    "    def countXorGreatThanEqual(self, num, limit):\n",
    "        total = sum(c.count for c in self.root.children if c is not None)\n",
    "        return total - self.countXorLessThan(num, limit)\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        child = defaultdict(list)\n",
    "        for i, v in enumerate(parents):\n",
    "            child[v].append(i)\n",
    "            if v == -1:\n",
    "                root = i\n",
    "        # print('rt', root)\n",
    "\n",
    "        ask = defaultdict(list)\n",
    "        for node, val in queries:\n",
    "            # tot[node] += 1\n",
    "            ask[node].append(val)\n",
    "        # print('child', child)\n",
    "        # print('ask', ask)\n",
    "        # print('root', root)\n",
    "        \n",
    "        ans = defaultdict(int)\n",
    "        # def dfs1(node):\n",
    "        #     for o in child[node]:\n",
    "        #         dfs(o)\n",
    "        #         tot[node] += tot[o]\n",
    "        # dfs1(0)\n",
    "\n",
    "        T = Trie()\n",
    "\n",
    "        def dfs2(node):\n",
    "            # print('node', node)\n",
    "            T.insert(node)\n",
    "            if ask[node]:\n",
    "                for val in ask[node]:\n",
    "                    ans[(node, val)] = T.maxXor(val)\n",
    "            \n",
    "            for o in child[node]:\n",
    "                dfs2(o)\n",
    "            T.delete(node)\n",
    "        \n",
    "        dfs2(root)\n",
    "\n",
    "        return [ans[(x, y)] for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0  # 子树大小\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 19\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 添加 val\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 删除 val，但不删除节点\n",
    "    # 要求 val 必须在 trie 中\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            cur = cur.children[(val >> i) & 1]\n",
    "            cur.cnt -= 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 返回 val 与 trie 中一个元素的最大异或和\n",
    "    # 要求 trie 中至少有一个元素 cnt\n",
    "    def max_xor(self, val: int) -> int:\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            # 如果 cur.children[bit^1].cnt == 0，视作空节点\n",
    "            # bit 为 1 应该选择 0 的路径,  bit 为 0 应该选择 1 的路径\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "\"\"\"\n",
    "   1. 从根开始不断进行深度优先搜索 深度优先搜索的当前路径的值才能保留  \n",
    "   2. 利用0-1Trie 对异或和进行更新即可\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        children = defaultdict(list)\n",
    "        root = -1\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = i\n",
    "                continue\n",
    "            children[p].append(i)\n",
    "        \n",
    "        k = len(queries)\n",
    "        ans = [0]*k\n",
    "        information = [[] for _ in range(n)]   # node 对应的(val, i)   i:答案数组的索引\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            information[node].append([val, i])\n",
    "        \n",
    "        t = Trie()\n",
    "        \n",
    "        def dfs(i):\n",
    "    \n",
    "            t.insert(i)\n",
    "            # 更新答案\n",
    "            for val, index in information[i]:\n",
    "                ans[index] = t.max_xor(val)\n",
    "            for child in children[i]:\n",
    "                dfs(child)\n",
    "            t.remove(i)\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class TrieBit:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        self.n = 22\n",
    "        return\n",
    "\n",
    "    def update(self, num):\n",
    "        cur = self.dct\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "            cur[\"cnt\"] = cur.get(\"cnt\", 0) + 1\n",
    "        return\n",
    "\n",
    "    def query(self, num):\n",
    "        cur = self.dct\n",
    "        ans = 0\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if 1 - w in cur:\n",
    "                cur = cur[1 - w]\n",
    "                ans += 1 << i\n",
    "            else:\n",
    "                cur = cur[w]\n",
    "        return ans\n",
    "\n",
    "    def delete(self, num):\n",
    "        cur = self.dct\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if cur[w].get(\"cnt\", 0) == 1:\n",
    "                del cur[w]\n",
    "                break\n",
    "            cur = cur[w]\n",
    "            cur[\"cnt\"] -= 1\n",
    "        return\n",
    "    \n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        root = -1\n",
    "        for i in range(n):\n",
    "            if parents[i] == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                dct[parents[i]].append(i)\n",
    "        \n",
    "        ind = [defaultdict(dict) for _ in range(n)]\n",
    "        for node, val in queries:\n",
    "            ind[node][val] = 0\n",
    "            \n",
    "        def dfs(i):\n",
    "            tree.update(i)\n",
    "            for v in ind[i]:\n",
    "                ind[i][v] = tree.query(v)\n",
    "            for j in dct[i]:\n",
    "                dfs(j)\n",
    "            tree.delete(i)\n",
    "            return \n",
    "        \n",
    "        tree = TrieBit()\n",
    "        dfs(root)\n",
    "        return [ind[node][v] for node, v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "##字典树\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left=None\n",
    "        self.right=None\n",
    "        self.cnt=0\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(parents)\n",
    "        MAXD=17\n",
    "        edges=defaultdict(list) ##表示树的结构，father：[child]\n",
    "        root=-1\n",
    "        for i,node in enumerate(parents):\n",
    "            if node==-1:\n",
    "               root=i\n",
    "            else:\n",
    "                edges[node].append(i)\n",
    "        q=len(queries)\n",
    "        ans=[0]*q\n",
    "        ##离线思想，用stored存储所有结点i对应的query\n",
    "        stored=defaultdict(list)\n",
    "        for i,(node,val) in enumerate(queries):\n",
    "            stored[node].append((i,val))\n",
    "        \n",
    "        r=Trie()\n",
    "        def add(num):\n",
    "            cur=r\n",
    "            for k in range(MAXD,-1,-1):\n",
    "                bit=(num>>k)&1  ##等价于num&(1<<k)，查询第k位是0还是1\n",
    "                if bit==0:\n",
    "                    if not cur.left:\n",
    "                        cur.left=Trie()\n",
    "                    cur=cur.left\n",
    "                else:\n",
    "                    if not cur.right:\n",
    "                        cur.right=Trie()\n",
    "                    cur=cur.right\n",
    "                cur.cnt+=1\n",
    "\n",
    "        def check(num):\n",
    "            cur,x=r,0\n",
    "            for k in range(MAXD,-1,-1):\n",
    "                bit=num&(1<<k)\n",
    "                if bit==0:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        x=x*2+1\n",
    "                        cur=cur.right\n",
    "                    else:\n",
    "                        x=x*2\n",
    "                        cur=cur.left\n",
    "                else:\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        x=x*2+1\n",
    "                        cur=cur.left\n",
    "                    else:\n",
    "                        x=x*2\n",
    "                        cur=cur.right\n",
    "            return x\n",
    "\n",
    "        def dele(num):\n",
    "            cur=r\n",
    "            for k in range(MAXD,-1,-1):\n",
    "                bit=num&(1<<k)\n",
    "                if bit==0:\n",
    "                    cur=cur.left\n",
    "                else:\n",
    "                    cur=cur.right\n",
    "                cur.cnt-=1\n",
    "\n",
    "        def dfs(u):\n",
    "            add(u)\n",
    "            for idx,num in stored[u]:\n",
    "                ans[idx]=check(num)\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            dele(u)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n",
    "# class Solution:\n",
    "#     def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ##暴力超时\n",
    "        # ans=[]\n",
    "        # for que in queries:\n",
    "        #     max_xor=float('-inf')\n",
    "        #     node,val=que[0],que[1]\n",
    "        #     while node!=-1:\n",
    "        #         xor=val^node\n",
    "        #         if xor>max_xor:\n",
    "        #             max_xor=xor\n",
    "        #         node=parents[node]\n",
    "        #     ans.append(max_xor)\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.cnt = 0\n",
    "    \n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        MAXD = 17\n",
    "        n = len(parents)\n",
    "        edges = defaultdict(list)\n",
    "\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i \n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        \n",
    "        q = len(queries)\n",
    "\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q \n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "        \n",
    "        r = Trie()\n",
    "\n",
    "        def add(x):\n",
    "            curr = r \n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "                if bit == 1:\n",
    "                    if not curr.right:\n",
    "                        curr.right = Trie()\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    if not curr.left:\n",
    "                        curr.left = Trie()\n",
    "                    curr = curr.left\n",
    "                curr.cnt += 1\n",
    "        \n",
    "        def check(x):\n",
    "            curr, ret = r, 0\n",
    "\n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "\n",
    "                if bit == 1:\n",
    "                    if curr.left and curr.left.cnt:\n",
    "                        ret |= (1 << k)\n",
    "                        curr = curr.left\n",
    "                    else:\n",
    "                        curr = curr.right\n",
    "                else:\n",
    "                    if curr.right and curr.right.cnt:\n",
    "                        ret |= (1 << k)\n",
    "                        curr = curr.right\n",
    "                    else:\n",
    "                        curr = curr.left\n",
    "            \n",
    "            return ret\n",
    "\n",
    "\n",
    "        def erase(x):\n",
    "            curr = r \n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "\n",
    "                if bit == 1:\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    curr = curr.left\n",
    "                curr.cnt -= 1\n",
    "\n",
    "        def dfs(u):\n",
    "            add(u)\n",
    "            for idx, x in stored[u]:\n",
    "                ans[idx] = check(x)\n",
    "\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            \n",
    "            erase(u)\n",
    "            \n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.cnt = 0\n",
    "    \n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        MAXD = 17\n",
    "        n = len(parents)\n",
    "        edges = defaultdict(list)\n",
    "\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i \n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        \n",
    "        q = len(queries)\n",
    "\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q \n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "        \n",
    "        r = Trie()\n",
    "\n",
    "        def add(x):\n",
    "            curr = r \n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "                if bit == 1:\n",
    "                    if not curr.right:\n",
    "                        curr.right = Trie()\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    if not curr.left:\n",
    "                        curr.left = Trie()\n",
    "                    curr = curr.left\n",
    "                curr.cnt += 1\n",
    "        \n",
    "        def check(x):\n",
    "            curr, ret = r, 0\n",
    "\n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "\n",
    "                if bit == 1:\n",
    "                    if curr.left and curr.left.cnt:\n",
    "                        ret += (1 << k)\n",
    "                        curr = curr.left\n",
    "                    else:\n",
    "                        curr = curr.right\n",
    "                else:\n",
    "                    if curr.right and curr.right.cnt:\n",
    "                        ret += (1 << k)\n",
    "                        curr = curr.right\n",
    "                    else:\n",
    "                        curr = curr.left\n",
    "            \n",
    "            return ret\n",
    "\n",
    "\n",
    "        def erase(x):\n",
    "            curr = r \n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "\n",
    "                if bit == 1:\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    curr = curr.left\n",
    "                curr.cnt -= 1\n",
    "\n",
    "        def dfs(u):\n",
    "            add(u)\n",
    "            for idx, x in stored[u]:\n",
    "                ans[idx] = check(x)\n",
    "\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            \n",
    "            erase(u)\n",
    "            \n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "##字典树\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left=None\n",
    "        self.right=None\n",
    "        self.cnt=0\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        MAXD=17\n",
    "        n=len(parents)\n",
    "        edges=defaultdict(list)\n",
    "        root=-1\n",
    "        for i,parent in enumerate(parents):\n",
    "            if parent==-1:\n",
    "                root=i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        q=len(queries)\n",
    "        stored=defaultdict(list)\n",
    "        ans=[0]*q\n",
    "        for i,(node,val) in enumerate(queries):\n",
    "            stored[node].append((i,val))\n",
    "        # print(edges,stored)\n",
    "\n",
    "        r=Trie()\n",
    "        def add(x):\n",
    "            cur=r\n",
    "            for i in range(MAXD,-1,-1):\n",
    "                if x&(1<<i):  ##1<<i就是2的i次方  (x<<i)&1\n",
    "                    if not cur.right:\n",
    "                        cur.right=Trie()\n",
    "                    cur=cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left=Trie()\n",
    "                    cur=cur.left\n",
    "                cur.cnt+=1\n",
    "        def check(x):\n",
    "            cur,ret=r,0\n",
    "            for i in range(MAXD,-1,-1):\n",
    "                if x&(1<<i):\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        ret|=(1<<i)\n",
    "                        cur=cur.left\n",
    "                    else:\n",
    "                        cur=cur.right\n",
    "                else:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret|=(1<<i)\n",
    "                        cur=cur.right\n",
    "                    else:\n",
    "                        cur=cur.left\n",
    "            return ret\n",
    "\n",
    "        def dele(x):\n",
    "            cur=r\n",
    "            for i in range(MAXD,-1,-1):\n",
    "                if x&(1<<i):\n",
    "                    cur=cur.right\n",
    "                else:\n",
    "                    cur=cur.left\n",
    "                cur.cnt-=1\n",
    "\n",
    "        def dfs(u):\n",
    "            add(u)\n",
    "            for idx,num in stored[u]:\n",
    "                ans[idx]=check(num)\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            dele(u)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ##暴力超时\n",
    "        # ans=[]\n",
    "        # for que in queries:\n",
    "        #     max_xor=float('-inf')\n",
    "        #     node,val=que[0],que[1]\n",
    "        #     while node!=-1:\n",
    "        #         xor=val^node\n",
    "        #         if xor>max_xor:\n",
    "        #             max_xor=xor\n",
    "        #         node=parents[node]\n",
    "        #     ans.append(max_xor)\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.cnt = 0\n",
    "    \n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        MAXD = 17\n",
    "        n = len(parents)\n",
    "        edges = defaultdict(list)\n",
    "\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i \n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        \n",
    "        q = len(queries)\n",
    "\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q \n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "        \n",
    "        r = Trie()\n",
    "\n",
    "        def add(x):\n",
    "            curr = r \n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "                if bit == 1:\n",
    "                    if not curr.right:\n",
    "                        curr.right = Trie()\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    if not curr.left:\n",
    "                        curr.left = Trie()\n",
    "                    curr = curr.left\n",
    "                curr.cnt += 1\n",
    "        \n",
    "        def check(x):\n",
    "            curr, ret = r, 0\n",
    "\n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "                if bit == 1:\n",
    "                    if curr.left and curr.left.cnt:\n",
    "                        curr = curr.left\n",
    "                        # ret += (1 << k)\n",
    "                        ret = ret * 2 + 1 \n",
    "                    else:\n",
    "                        curr = curr.right\n",
    "                        ret *= 2\n",
    "                    \n",
    "                else:\n",
    "                    if curr.right and curr.right.cnt:\n",
    "                        curr = curr.right\n",
    "                        # ret += (1 << k)\n",
    "                        ret = ret * 2 + 1\n",
    "                    else:\n",
    "                        curr = curr.left\n",
    "                        ret *= 2\n",
    "\n",
    "            return ret\n",
    "\n",
    "\n",
    "        def erase(x):\n",
    "            curr = r \n",
    "            for k in range(MAXD, -1, -1):\n",
    "                bit = (x >> k) & 1\n",
    "                if bit == 1:\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    curr = curr.left\n",
    "                curr.cnt -= 1\n",
    "\n",
    "        def dfs(u):\n",
    "            add(u)\n",
    "            for idx, x in stored[u]:\n",
    "                ans[idx] = check(x)\n",
    "            \n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            erase(u)\n",
    "            \n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 2\n",
    "        self.cnt = 0\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = self\n",
    "        v = bin(num)[2:]\n",
    "        word = '0' * (32 - len(v)) + v\n",
    "        for ch in word:\n",
    "            idx = int(ch)\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def delete(self, num):\n",
    "        node = self\n",
    "        v = bin(num)[2:]\n",
    "        word = '0' * (32 - len(v)) + v\n",
    "        for ch in word:\n",
    "            idx = int(ch)\n",
    "            node = node.children[idx]\n",
    "            node.cnt -= 1\n",
    "    \n",
    "    def cal(self, num):\n",
    "        node = self\n",
    "        v = bin(num)[2:]\n",
    "        word = '0' * (32 - len(v)) + v\n",
    "        res = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            idx = int(ch)\n",
    "            re = idx ^ 1\n",
    "            if node.children[re] and node.children[re].cnt > 0:\n",
    "                node = node.children[re]\n",
    "                res |= 1 << (31 - i)\n",
    "            else:\n",
    "                node = node.children[idx]\n",
    "        \n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                root = i\n",
    "        \n",
    "        t = Trie()\n",
    "        dic = defaultdict(list)\n",
    "        for i, (q, v) in enumerate(queries):\n",
    "            dic[q].append((i, v))\n",
    "        \n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(node):\n",
    "            t.insert(node)\n",
    "            for i, v in dic[node]:\n",
    "                ans[i] = t.cal(v)\n",
    "\n",
    "            for ch in g[node]:\n",
    "                dfs(ch)\n",
    "            \n",
    "            t.delete(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 2\n",
    "        # 经过当前节点的数的数量\n",
    "        self.cnt = 0\n",
    "        # 给定数据范围的最高二进制位数\n",
    "        self.high_bit = 18\n",
    "\n",
    "    def insert(self, x):\n",
    "        '''将数字 x 按照二进制位从高到低的顺序插入到字典树中'''\n",
    "        node = self\n",
    "        for i in range(self.high_bit, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            if node.children[v] is None:\n",
    "                node.children[v] = Trie()\n",
    "            node = node.children[v]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def delete(self, x):\n",
    "        '''删去一个数字 x'''\n",
    "        node = self\n",
    "        for i in range(self.high_bit, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            node = node.children[v]\n",
    "            node.cnt -= 1\n",
    "\n",
    "    def searchXorMax(self, x):\n",
    "        '''查找字典树中的数与 x 异或后最大值'''\n",
    "        node = self\n",
    "        res = 0\n",
    "        for i in range(self.high_bit, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            re = v ^ 1\n",
    "            if node.children[re] and node.children[re].cnt > 0:\n",
    "                node = node.children[re]\n",
    "                res |= 1 << i\n",
    "            else:\n",
    "                node = node.children[v]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                root = i\n",
    "\n",
    "        t = Trie()\n",
    "        dic = defaultdict(list)\n",
    "        for i, (q, v) in enumerate(queries):\n",
    "            dic[q].append((i, v))\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(node):\n",
    "            t.insert(node)\n",
    "            for i, v in dic[node]:\n",
    "                ans[i] = t.searchXorMax(v)\n",
    "            for ch in g[node]:\n",
    "                dfs(ch)\n",
    "            t.delete(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 2\n",
    "        self.cnt = 0\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = self\n",
    "        v = bin(num)[2:]\n",
    "        word = '0' * (18 - len(v)) + v\n",
    "        for ch in word:\n",
    "            idx = int(ch)\n",
    "            if not node.children[idx]:\n",
    "                node.children[idx] = Trie()\n",
    "            node = node.children[idx]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def delete(self, num):\n",
    "        node = self\n",
    "        v = bin(num)[2:]\n",
    "        word = '0' * (18 - len(v)) + v\n",
    "        for ch in word:\n",
    "            idx = int(ch)\n",
    "            node = node.children[idx]\n",
    "            node.cnt -= 1\n",
    "    \n",
    "    def cal(self, num):\n",
    "        node = self\n",
    "        v = bin(num)[2:]\n",
    "        word = '0' * (18 - len(v)) + v\n",
    "        res = 0\n",
    "        for i, ch in enumerate(word):\n",
    "            idx = int(ch)\n",
    "            re = idx ^ 1\n",
    "            if node.children[re] and node.children[re].cnt > 0:\n",
    "                node = node.children[re]\n",
    "                res |= 1 << (17 - i)\n",
    "            else:\n",
    "                node = node.children[idx]\n",
    "        \n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "            else:\n",
    "                root = i\n",
    "        \n",
    "        t = Trie()\n",
    "        dic = defaultdict(list)\n",
    "        for i, (q, v) in enumerate(queries):\n",
    "            dic[q].append((i, v))\n",
    "        \n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(node):\n",
    "            t.insert(node)\n",
    "            for i, v in dic[node]:\n",
    "                ans[i] = t.cal(v)\n",
    "\n",
    "            for ch in g[node]:\n",
    "                dfs(ch)\n",
    "            \n",
    "            t.delete(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode1:\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.children = []\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    MAX_BIT = 17\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 添加元素\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if not cur.children[bit]:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1\n",
    "\n",
    "    # 移除元素，只设置cnt，并不移除Node\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt -= 1\n",
    "\n",
    "    # 计算与字典树中的所有元素最大异或值\n",
    "    def max_xor(self, val: int) -> int:\n",
    "        ans = 0\n",
    "        cur = self.root\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            if not cur:\n",
    "                break\n",
    "            bit = (val >> i) & 1\n",
    "            # 尝试设置第i位为1\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q_map = defaultdict(list)\n",
    "        for i, q in enumerate(queries):\n",
    "            q_map[q[0]].append((q[1], i))\n",
    "        n = len(parents)\n",
    "        nodes = [TreeNode1(v) for v in range(n)]\n",
    "        # build tree\n",
    "        root = nodes[0]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = nodes[i]\n",
    "                continue\n",
    "            # 可能为n叉树\n",
    "            nodes[p].children.append(nodes[i])\n",
    "\n",
    "        t = Trie()\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(cur: TreeNode1) -> None:\n",
    "            t.insert(cur.val)\n",
    "            if cur.val in q_map:\n",
    "                for v, i in q_map[cur.val]:\n",
    "                    ans[i] = t.max_xor(v)\n",
    "            for node in cur.children:\n",
    "                dfs(node)\n",
    "            t.remove(cur.val)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):     #左0右1\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.cnt = 0        #以这个点结尾的次数\n",
    "    \n",
    "    def insert(self, x: int) -> None:\n",
    "        root = self\n",
    "        for i in range(17, -1, -1):\n",
    "            if (x >> i) & 1:\n",
    "                if root.right == None:\n",
    "                    root.right = Trie()\n",
    "                root = root.right\n",
    "                root.cnt += 1\n",
    "            else:\n",
    "                if root.left == None:\n",
    "                    root.left = Trie()\n",
    "                root = root.left\n",
    "                root.cnt += 1\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        root = self\n",
    "        res = 0\n",
    "        for i in range(17, -1, -1):\n",
    "            if (x >> i) & 1:\n",
    "                if root.left and root.left.cnt > 0:\n",
    "                    root = root.left\n",
    "                    res = 2 * res + 1\n",
    "                else:\n",
    "                    root = root.right\n",
    "                    res = 2 * res\n",
    "            else:\n",
    "                if root.right and root.right.cnt > 0:\n",
    "                    root = root.right\n",
    "                    res = 2 * res + 1\n",
    "                else:\n",
    "                    root = root.left\n",
    "                    res = 2 * res\n",
    "        return res\n",
    "\n",
    "    def delete(self, x: int) -> int:\n",
    "        root = self\n",
    "        for i in range(17, -1, -1):\n",
    "            if (x >> i) & 1 :\n",
    "                root = root.right\n",
    "                root.cnt -= 1\n",
    "            else:\n",
    "                root = root.left\n",
    "                root.cnt -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        father_child = defaultdict(list)\n",
    "        root = -1\n",
    "        for x, father in enumerate(parents):\n",
    "            if father == -1:\n",
    "                root = x\n",
    "            else:\n",
    "                father_child[father].append(x)\n",
    "        \n",
    "        qn = len(queries)\n",
    "        node__i_val = defaultdict(list)\n",
    "        for i in range(qn):\n",
    "            node, val = queries[i]\n",
    "            node__i_val[node].append((i, val))\n",
    "\n",
    "        T = Trie()\n",
    "        res = [0 for _ in range(qn)]\n",
    "\n",
    "        def backtrace(x: int) -> None:\n",
    "            T.insert(x)\n",
    "            for qi, val in node__i_val[x]:\n",
    "                res[qi] = T.query(val)\n",
    "            for y in father_child[x]:\n",
    "                backtrace(y)\n",
    "            T.delete(x)\n",
    "\n",
    "        backtrace(root)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    output = []\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        self.output=[0]*len(queries)\n",
    "        children = {}\n",
    "        left_child, right_child = [-1]*len(parents),[-1]*len(parents)\n",
    "        root = parents.index(-1)\n",
    "        cur_stack = [root]\n",
    "\n",
    "        gene_dict = {}\n",
    "        #Construct the tree\n",
    "        self.tree_construct(parents,children)\n",
    "        #Try to set queries\n",
    "        queries_set = {}\n",
    "        index = 0\n",
    "        for arr in queries:\n",
    "            if arr[0] not in queries_set:\n",
    "                queries_set[arr[0]] = []\n",
    "            queries_set[arr[0]].append([index,self.to_18_bin(arr[1])])\n",
    "            index+=1\n",
    "        #DFS\n",
    "\n",
    "        # print(children)\n",
    "        # print(queries_set)\n",
    "        self.dict_add(gene_dict,self.to_18_bin(root))\n",
    "        \n",
    "        self.DFS_travel(root,children,queries_set,gene_dict)\n",
    "        return self.output\n",
    "\n",
    "\n",
    "\n",
    "    #Transfer number to binary\n",
    "    def to_18_bin(self,num:int)->str:\n",
    "        str_n = bin(num)[2:]\n",
    "        return \"0\"*(18-len(str_n))+str_n\n",
    "\n",
    "    #Construct the tree\n",
    "    def tree_construct(self,parents:list,children:dict):\n",
    "        for i in range(len(parents)):\n",
    "            children[i] = []\n",
    "        for i in range(len(parents)):\n",
    "            if parents[i]!=-1:\n",
    "                if parents[i] not in children:\n",
    "                    children[parents[i]] = []\n",
    "                children[parents[i]].append(i)\n",
    "\n",
    "    #DFS_travel\n",
    "    def DFS_travel(self,cur_node:int,children : dict,queries_set:dict,gene_dict:dict):\n",
    "        #print(cur_stack)\n",
    "\n",
    "        for child in children[cur_node]:\n",
    "\n",
    "\n",
    "            self.dict_add(gene_dict,self.to_18_bin(child))\n",
    "            self.DFS_travel(child,children,queries_set,gene_dict)\n",
    "\n",
    "        #print(cur_stack,\"now\")\n",
    "        #Right now we are going to pop out the key node, before it, we search the max val  \n",
    "        if cur_node in queries_set:\n",
    "            for tmp_arr in queries_set[cur_node]:\n",
    "                self.output[tmp_arr[0]] = self.search_max_genetic_diff(gene_dict,tmp_arr[1] ) \n",
    "\n",
    "            #Pop it out and delete\n",
    "            # outnode = cur_stack.pop()  \n",
    "            #print(gene_dict)\n",
    "            # print(outnode)     \n",
    "            # print(self.output)\n",
    "            \n",
    "        self.dict_delete(gene_dict,self.to_18_bin(cur_node))\n",
    "\n",
    "\n",
    "    #search func\n",
    "    def search_max_genetic_diff(self,gene_dict : dict,val : str )->int:\n",
    "        cur_dict_node = gene_dict\n",
    "        find_str = \"\"\n",
    "        for bits in val:\n",
    "            if bits==\"0\":\n",
    "                if \"1\" in cur_dict_node:\n",
    "                    cur_dict_node = cur_dict_node[\"1\"]\n",
    "                    find_str+=\"1\"\n",
    "                else:\n",
    "                    cur_dict_node = cur_dict_node[\"0\"]\n",
    "                    find_str+=\"0\"\n",
    "            else:\n",
    "                if \"0\" in cur_dict_node:\n",
    "                    cur_dict_node = cur_dict_node[\"0\"]\n",
    "                    find_str+=\"0\"\n",
    "                else:\n",
    "                    cur_dict_node = cur_dict_node[\"1\"]\n",
    "                    find_str+=\"1\"\n",
    "        return int(find_str,2)^int(val,2)\n",
    "    #gene_dict tree, construct, add, delete\n",
    "    def dict_add(self,gene_dict:dict,word:str):\n",
    "        #print(word)\n",
    "        cur_dict_node = gene_dict\n",
    "        for w in word:\n",
    "            if w not in cur_dict_node:\n",
    "                cur_dict_node[w]={}\n",
    "                cur_dict_node[w][\"counter\"] = 0\n",
    "            \n",
    "            cur_dict_node=cur_dict_node[w]\n",
    "            cur_dict_node[\"counter\"] += 1\n",
    "    \n",
    "    def dict_delete(self,gene_dict:dict,word:str):\n",
    "        cur_dict_node = gene_dict\n",
    "        for w in word:\n",
    "            \n",
    "            next_dict_node=cur_dict_node[w]\n",
    "            if next_dict_node[\"counter\"] == 1:\n",
    "                del cur_dict_node[w]\n",
    "                break;\n",
    "            else:\n",
    "                cur_dict_node=cur_dict_node[w]\n",
    "                cur_dict_node[\"counter\"] -= 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "from typing import List\n",
    "\n",
    "'''  \n",
    "题目名 5816. 查询最大基因差  \n",
    "思路 离线计算，对于询问，按照节点进行分桶，DFS遍历整个树，每到一个节点将节点上的数加入到Trie, 回溯时候将数值删掉，检查到当前前是询问中包含  \n",
    "的点，就计算该点的所有询问，计算询问的方式就是简单的前缀树求最大异或和问题  \n",
    "'''\n",
    "\n",
    "from typing import List\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999999)\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.next = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def add_val(self, val):\n",
    "        cur = self.root\n",
    "        for i in range(17, -1, -1):\n",
    "            ch = 0 if val & (1 << i) == 0 else 1\n",
    "            if cur.next[ch] is None:\n",
    "                new_node = TrieNode()\n",
    "                cur.next[ch] = new_node\n",
    "            cur = cur.next[ch]\n",
    "            cur.cnt += 1\n",
    "\n",
    "    def del_val(self, val):\n",
    "        cur = self.root\n",
    "        for i in range(17, -1, -1):\n",
    "            ch = 0 if val & (1 << i) == 0 else 1\n",
    "\n",
    "            cur.next[ch].cnt -= 1\n",
    "            if cur.next[ch].cnt != 0:\n",
    "                cur = cur.next[ch]\n",
    "            else:\n",
    "                cur.next[ch] = None\n",
    "                break\n",
    "\n",
    "    def getRoot(self) -> TrieNode:\n",
    "        return self.root\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        qq = {}\n",
    "        link = {i: [] for i in range(len(parents))}\n",
    "\n",
    "        for idx, (node, val) in enumerate(queries):\n",
    "            if node not in qq:\n",
    "                qq[node] = []\n",
    "            qq[node].append((val, idx))\n",
    "\n",
    "        root = None\n",
    "        for node, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = node\n",
    "            else:\n",
    "                link[p].append(node)\n",
    "\n",
    "        valid = [False] * len(parents)\n",
    "\n",
    "        def dfs(node):\n",
    "            flag = False\n",
    "            if node in qq.keys():\n",
    "                flag = True\n",
    "\n",
    "            cnt = 0\n",
    "            for ne in link[node]:\n",
    "                if dfs(ne):\n",
    "                    cnt += 1\n",
    "\n",
    "            if flag or cnt > 0:\n",
    "                valid[node] = True\n",
    "\n",
    "            return valid[node]\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        trie = Trie()\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        def solve(node):\n",
    "            if valid[node] == False:\n",
    "                return\n",
    "\n",
    "            trie.add_val(node)\n",
    "            if node in qq.keys():\n",
    "                for val, idx in qq[node]:\n",
    "                    cur = trie.getRoot()\n",
    "                    ans = 0\n",
    "                    for i in range(18):\n",
    "                        if val & (1 << (17 - i)) == 0:\n",
    "                            if cur.next[1] is not None:\n",
    "                                cur = cur.next[1]\n",
    "                                ans |= (1 << (17 - i))\n",
    "                            else:\n",
    "                                cur = cur.next[0]\n",
    "                        else:\n",
    "                            if cur.next[0] is not None:\n",
    "                                cur = cur.next[0]\n",
    "                                ans |= (1 << (17 - i))\n",
    "                            else:\n",
    "                                cur = cur.next[1]\n",
    "\n",
    "                    ret[idx] = max(ret[idx], ans)\n",
    "\n",
    "            for ne in link[node]:\n",
    "                solve(ne)\n",
    "\n",
    "            trie.del_val(node)\n",
    "\n",
    "        solve(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tire:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.child = [None] * 2\n",
    "        self.cnt = 0\n",
    "        self.MX = 17\n",
    "\n",
    "    def add(self, x):\n",
    "        node = self\n",
    "        for i in range(self.MX, -1, -1):\n",
    "            cur = x >> i & 1\n",
    "            if not node.child[cur]:\n",
    "                node.child[cur] = Tire()\n",
    "            node = node.child[cur]\n",
    "            node.cnt += 1\n",
    "    \n",
    "    def erase(self, x):\n",
    "        node = self\n",
    "        for i in range(self.MX, -1, -1):\n",
    "            cur = x >> i & 1\n",
    "            node = node.child[cur]\n",
    "            node.cnt -= 1\n",
    "\n",
    "    def query(self, x):\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(self.MX, -1, -1):\n",
    "            cur = x >> i & 1\n",
    "            if node.child[cur ^ 1] and node.child[cur ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                node = node.child[cur ^ 1]\n",
    "            else:\n",
    "                node = node.child[cur]\n",
    "        return ans  \n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        root = -1\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                g[p].append(i)\n",
    "        \n",
    "        d = defaultdict(list)\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            d[node].append((i, val))\n",
    "\n",
    "        t = Tire()\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(node):\n",
    "            t.add(node)\n",
    "            for i, val in d[node]:\n",
    "                ans[i] = t.query(val)\n",
    "            for p in g[node]:\n",
    "                dfs(p)\n",
    "            t.erase(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = [None,None]\n",
    "        self.cnt = 0\n",
    "\n",
    "class Trie:\n",
    "    MAX_BIT = 20\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "        self.cnt = 0\n",
    "    def insert(self,num):\n",
    "        cur = self.root\n",
    "        cur.cnt += 1\n",
    "        for i in range(self.MAX_BIT,-1,-1):\n",
    "             v = (num >> i) & 1\n",
    "             if not cur.children[v]:\n",
    "                 cur.children[v] = Node()\n",
    "             cur = cur.children[v]\n",
    "             cur.cnt += 1\n",
    "\n",
    "    def  remove(self, num):\n",
    "        cur = self.root\n",
    "        cur.cnt -= 1\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            v = (num >> i) & 1\n",
    "            cur = cur.children[v]\n",
    "            cur.cnt -= 1\n",
    "    def max_xor(self,num):\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(self.MAX_BIT,-1,-1):\n",
    "            cv = (num >> i) & 1\n",
    "            if cur.children[cv ^ 1] and cur.children[cv ^ 1].cnt > 0:\n",
    "                cur = cur.children[cv ^ 1]\n",
    "                ans |= (1<<i)\n",
    "            else:\n",
    "                cur = cur.children[cv]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents, queries) :\n",
    "     \n",
    "        i = 0\n",
    "        graph = defaultdict(list)\n",
    "        qs = defaultdict(list)\n",
    "        r = -1\n",
    "        for  j in range(len(parents)):\n",
    "            if parents[j] != -1:\n",
    "                graph[parents[j]].append(j)\n",
    "            else:\n",
    "                r = j\n",
    "        \n",
    "        for i,(q,val) in enumerate(queries):\n",
    "            qs[q].append([val,i])\n",
    "        t = Trie()\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        def dfs(cur):\n",
    "            nonlocal qs\n",
    "            t.insert(cur)\n",
    "            for q,idx in qs[cur]:\n",
    "                res[idx] = t.max_xor(q)\n",
    "            for nei in graph[cur]:\n",
    "                dfs(nei)\n",
    "            t.remove(cur)\n",
    "        dfs(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tire:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.child = [None] * 2\n",
    "        self.cnt = 0\n",
    "        self.MX = 17\n",
    "\n",
    "    def add(self, x):\n",
    "        node = self\n",
    "        for i in range(self.MX, -1, -1):\n",
    "            cur = x >> i & 1\n",
    "            if not node.child[cur]:\n",
    "                node.child[cur] = Tire()\n",
    "            node = node.child[cur]\n",
    "            node.cnt += 1\n",
    "    \n",
    "    def erase(self, x):\n",
    "        node = self\n",
    "        for i in range(self.MX, -1, -1):\n",
    "            cur = x >> i & 1\n",
    "            node = node.child[cur]\n",
    "            node.cnt -= 1\n",
    "\n",
    "    def query(self, x):\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(self.MX, -1, -1):\n",
    "            cur = x >> i & 1\n",
    "            if node.child[cur ^ 1] and node.child[cur ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                node = node.child[cur ^ 1]\n",
    "            else:\n",
    "                node = node.child[cur]\n",
    "        return ans  \n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        root = -1\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                g[p].append(i)\n",
    "        \n",
    "        d = defaultdict(list)\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            d[node].append((i, val))\n",
    "\n",
    "        t = Tire()\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def dfs(node):\n",
    "            t.add(node)\n",
    "            for i, val in d[node]:\n",
    "                ans[i] = t.query(val)\n",
    "            for p in g[node]:\n",
    "                dfs(p)\n",
    "            t.erase(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    left: \"TrieNode\" = None\n",
    "    right: \"TrieNode\" = None\n",
    "    cnt: int  = 0    # 因此这里使用 cnt 变量进行记录该节点对应的数的个数\n",
    "    nums: int = -1\n",
    "\n",
    "class Trie:\n",
    "    MAXD = 31\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        # 初始化根节点\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    # 向p所在的字典树添加一个数 x， 位数为MAXD\n",
    "    def trie_insert(self, x: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(self.MAXD, -1, -1):\n",
    "            if x & (1 << i):\n",
    "                if not cur.right:\n",
    "                    cur.right = TrieNode()\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                if not cur.left:\n",
    "                    cur.left = TrieNode()\n",
    "                cur = cur.left\n",
    "            cur.cnt += 1\n",
    "        cur.nums=x\n",
    "\n",
    "    # 从字典树中删除一个数\n",
    "    def trie_erase(self , x: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(self.MAXD, -1, -1):\n",
    "            if x & (1 << i):\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                cur = cur.left\n",
    "            cur.cnt -= 1\n",
    "        cur.nums = -1\n",
    "\n",
    "    # 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值\n",
    "    def trie_query(self, x: int) -> int:\n",
    "        cur, ret = self.root, 0\n",
    "        for i in range(self.MAXD, -1, -1):\n",
    "            if x & (1 << i):            #要去查找当前节点的找相反的方向，这样才能在当前位置的 xor 得到最大值\n",
    "                if cur.left and cur.left.cnt:\n",
    "                    ret |= (1 << i)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = cur.right\n",
    "            else:\n",
    "                if cur.right and cur.right.cnt:\n",
    "                    ret |= (1 << i)\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "        #如果需要返回参与最大异或值计算的那个数是哪一个， 则返回 cur.nums\n",
    "        #return cur.nums\n",
    "        return ret\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: [int], queries: [[int]]) -> [int]:\n",
    "        qu = defaultdict(list)\n",
    "        for i in range(len(queries)):\n",
    "            qu[queries[i][0]].append((i,queries[i][1]))\n",
    "\n",
    "        root=-1\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n):  # 节点编号从 0 开始, 默认将0设置为根节点\n",
    "            if parents[i]!=-1:\n",
    "                g[i].append(parents[i])\n",
    "                g[parents[i]].append(i)\n",
    "            else:\n",
    "                root=i\n",
    "\n",
    "        dc=[0 for i in range(len(queries))]\n",
    "\n",
    "        tree=Trie()\n",
    "#        print(g)\n",
    "#        print(qu)\n",
    "\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "\n",
    "            tree.trie_insert(x)\n",
    "            #查询以x为点的查询\n",
    "            for pos,point in qu[x]:\n",
    "                tmp=tree.trie_query(point)\n",
    "                dc[pos]=tmp\n",
    "\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "            tree.trie_erase(x)\n",
    "\n",
    "        dfs(root, -1)\n",
    "        return dc\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tire:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.child = [None] * 2\n",
    "        self.cnt = 0\n",
    "  \n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        root = -1\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                g[p].append(i)\n",
    "        MX = 17\n",
    "        d = defaultdict(list)\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            d[node].append((i, val))\n",
    "\n",
    "        t = Tire()\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        def add(x):\n",
    "            node = t\n",
    "            for i in range(MX, -1, -1):\n",
    "                cur = x >> i & 1\n",
    "                if not node.child[cur]:\n",
    "                    node.child[cur] = Tire()\n",
    "                node = node.child[cur]\n",
    "                node.cnt += 1\n",
    "    \n",
    "        def erase(x):\n",
    "            node = t\n",
    "            for i in range(MX, -1, -1):\n",
    "                cur = x >> i & 1\n",
    "                node = node.child[cur]\n",
    "                node.cnt -= 1\n",
    "\n",
    "        def query(x):\n",
    "            node = t\n",
    "            ans = 0\n",
    "            for i in range(MX, -1, -1):\n",
    "                cur = x >> i & 1\n",
    "                if node.child[cur ^ 1] and node.child[cur ^ 1].cnt:\n",
    "                    ans |= 1 << i\n",
    "                    node = node.child[cur ^ 1]\n",
    "                else:\n",
    "                    node = node.child[cur]\n",
    "            return ans\n",
    "\n",
    "        def dfs(node):\n",
    "            add(node)\n",
    "            for i, val in d[node]:\n",
    "                ans[i] = query(val)\n",
    "            for p in g[node]:\n",
    "                dfs(p)\n",
    "            erase(node)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.count = 0\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, root, num):\n",
    "        node = root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if bit not in node.children:\n",
    "                node.children[bit] = TrieNode()\n",
    "            node = node.children[bit]\n",
    "            node.count += 1\n",
    "            \n",
    "    def remove(self, root, num):\n",
    "        node = root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            node = node.children[bit]\n",
    "            node.count -= 1\n",
    "            \n",
    "    def query(self, root, num):\n",
    "        node = root\n",
    "        ans = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            oppo = 1 - bit\n",
    "            if oppo in node.children and node.children[oppo].count > 0:\n",
    "                ans |= (1 << i)\n",
    "                node = node.children[oppo]\n",
    "            else:\n",
    "                node = node.children[bit]\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, root, trie, adj_list, queries, ans):\n",
    "        self.insert(trie, root)\n",
    "        \n",
    "        if root in queries:\n",
    "            for val, idx in queries[root]:\n",
    "                ans[idx] = self.query(trie, val)\n",
    "        \n",
    "        if root in adj_list:  # Check if the node has children\n",
    "            for child in adj_list[root]:\n",
    "                self.dfs(child, trie, adj_list, queries, ans)\n",
    "        \n",
    "        self.remove(trie, root)\n",
    "        \n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        root = -1\n",
    "        adj_list = {}\n",
    "        query_dict = {}\n",
    "        \n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "                continue\n",
    "            if parent not in adj_list:\n",
    "                adj_list[parent] = []\n",
    "            adj_list[parent].append(i)\n",
    "            \n",
    "        for idx, (node, val) in enumerate(queries):\n",
    "            if node not in query_dict:\n",
    "                query_dict[node] = []\n",
    "            query_dict[node].append((val, idx))\n",
    "        \n",
    "        ans = [0] * len(queries)\n",
    "        trie = TrieNode()\n",
    "        self.dfs(root, trie, adj_list, query_dict, ans)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    # 这里字典树需要支持删除操作\n",
    "    # 所以用cnt变量来记录该节点所对应的数的个数\n",
    "    cnt: int = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # 最大的数的二进制表示不会超过18位\n",
    "    # 那么二进制位的下标范围是[0, 17]\n",
    "    MAXD = 17\n",
    "\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "\n",
    "        # 将parents存储为树的形式，方便进行深度优先遍历\n",
    "        edges = defaultdict(list) # 孩子节点, \n",
    "        # 找出根节点\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        \n",
    "        q = len(queries)\n",
    "        # 使用离线的思想，stored[i] 存储了所有节点i对应的询问\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val)) # 起点node, 第i个询问, 被异或值val\n",
    "\n",
    "        r = Trie() # 字典树的根节点\n",
    "\n",
    "        # 向字典树添加一个数\n",
    "        def trie_insert(x: int) -> None: # 形成x的数位字典树（从最高位开始）\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1): # 从最高位开始形成树\n",
    "                if x & (1 << i): # 取出x的第i位, 如果是1, 延伸右节点\n",
    "                    if not cur.right: # 如果右节点不存在\n",
    "                        cur.right = Trie() # 生成右节点\n",
    "                    cur = cur.right # 到右节点去\n",
    "                else:  # 如果x的第i位是0。那么延伸左节点\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left # 到最前沿去\n",
    "                cur.cnt += 1 # 当前位置加入了一个点。\n",
    "        \n",
    "        # 对于给定的x，返回字典树中包含的数与x进行异或运算可以达到的最大值\n",
    "        def trie_query(x: int) -> int:\n",
    "            cur, ret = r, 0\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i): # 取出第i位, 且如果是1, 找0累加（因为是异或）。\n",
    "                    if cur.left and cur.left.cnt: # 如果这个节点存在，而且后续有节点(包括该节点)。\n",
    "                        ret |= (1 << i) # 这一位置1 \n",
    "                        cur = cur.left # 继续向左\n",
    "                    else:  # 这条路结束了，只能转向了。\n",
    "                        cur = cur.right \n",
    "                else: # 第i位是0, 那向右找1\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret |= (1 << i) # 这一位置1 ， 表示这一位满足要求（能取到）。\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return ret \n",
    "\n",
    "        # 从字典树中删除一个数\n",
    "        def trie_erase(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i): # 取出第i位是1\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1 # 删除他的痕迹（痕迹是指，自他而下的都会+1）\n",
    "\n",
    "        def dfs(u: int) -> None:\n",
    "            trie_insert(u) # 向字典树添加一个数 u\n",
    "            for idx, num in stored[u]: # 对于root的所有询问（如果有）， 遍历字典树（异或）计算他们的结果\n",
    "                ans[idx] = trie_query(num)\n",
    "            for v in edges[u]: # u的孩子，继续搞下去。\n",
    "                dfs(v)\n",
    "            trie_erase(u)\n",
    "        \n",
    "        dfs(root) # 从根节点进入\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    # 这里字典树需要支持删除操作\n",
    "    # 所以用cnt变量来记录该节点所对应的数的个数\n",
    "    cnt: int = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # 最大的数的二进制表示不会超过18位\n",
    "    # 那么二进制位的下标范围是[0, 17]\n",
    "    MAXD = 17\n",
    "\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "\n",
    "        # 将parents存储为树的形式，方便进行深度优先遍历\n",
    "        edges = defaultdict(list) # 孩子节点, \n",
    "        # 找出根节点\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        \n",
    "        q = len(queries)\n",
    "        # 使用离线的思想，stored[i] 存储了所有节点i对应的询问\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val)) # 起点node, 第i个询问, 被异或值val\n",
    "\n",
    "        r = Trie() # 字典树的根节点\n",
    "\n",
    "        # 向字典树添加一个数\n",
    "        def trie_insert(x: int) -> None: # 形成x的数位字典树（从最高位开始）\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1): # 从最高位开始形成树\n",
    "                if x & (1 << i): # 取出x的第i位, 如果是1, 延伸右节点\n",
    "                    if not cur.right: # 如果右节点不存在\n",
    "                        cur.right = Trie() # 生成右节点\n",
    "                    cur = cur.right # 到右节点去\n",
    "                else:  # 如果x的第i位是0。那么延伸左节点\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left # 到最前沿去\n",
    "                cur.cnt += 1 # 当前位置加入了一个点。\n",
    "        \n",
    "        # 对于给定的x，返回字典树中包含的数与x进行异或运算可以达到的最大值\n",
    "        def trie_query(x: int) -> int:\n",
    "            cur, ret = r, 0\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i): # 取出第i位, 且如果是1, 找0累加（因为是异或）。\n",
    "                    if cur.left and cur.left.cnt: # 如果这个节点存在，而且后续有节点(包括该节点)。\n",
    "                        ret |= (1 << i) # 这一位置1 \n",
    "                        cur = cur.left # 继续向左\n",
    "                    else:  # 这条路结束了，只能转向了。\n",
    "                        cur = cur.right \n",
    "                else: # 第i位是0, 那向右找1\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret |= (1 << i) # 这一位置1 ， 表示这一位满足要求（能取到）。\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return ret \n",
    "\n",
    "        # 从字典树中删除一个数\n",
    "        def trie_erase(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i): # 取出第i位是1\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1 # 删除他的痕迹（痕迹是指，自他而下的都会+1）\n",
    "\n",
    "        def dfs(u: int) -> None:\n",
    "            trie_insert(u) # 向字典树添加一个数 u\n",
    "            for idx, num in stored[u]: # 对于root的所有询问（如果有）， 遍历字典树（异或）计算他们的结果\n",
    "                ans[idx] = trie_query(num)\n",
    "            for v in edges[u]: # u的孩子，继续搞下去。\n",
    "                dfs(v)\n",
    "            trie_erase(u)\n",
    "        \n",
    "        dfs(root) # 从根节点进入\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    # 由于我们的字典树需要支持删除数的操作\n",
    "    # 因此这里使用 cnt 变量进行记录该节点对应的数的个数\n",
    "    cnt: int = 0\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # 最大的数的二进制表示不会超过 18 位\n",
    "    # 那么二进制位的下标范围为 [0, 17]\n",
    "    MAXD = 17\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "\n",
    "        # 将 parents 存储为树的形式，方便进行深度优先遍历\n",
    "        edges = defaultdict(list)\n",
    "        # 找出根节点\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "\n",
    "        q = len(queries)\n",
    "        # 使用离线的思想，stored[i] 存储了所有节点 i 对应的询问\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "\n",
    "        r = Trie()\n",
    "\n",
    "        # 向字典树添加一个数\n",
    "        def trie_insert(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                cur.cnt += 1\n",
    "\n",
    "        # 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值\n",
    "        def trie_query(x: int) -> int:\n",
    "            cur, ret = r, 0\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                else:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return ret\n",
    "\n",
    "        # 从字典树中删除一个数\n",
    "        def trie_erase(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1\n",
    "\n",
    "        # 深度优先遍历\n",
    "        def dfs(u: int) -> None:\n",
    "            trie_insert(u)\n",
    "            for idx, num in stored[u]:\n",
    "                ans[idx] = trie_query(num)\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            trie_erase(u)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    # 由于我们的字典树需要支持删除数的操作\n",
    "    # 因此这里使用 cnt 变量进行记录该节点对应的数的个数\n",
    "    cnt: int = 0\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # 最大的数的二进制表示不会超过 18 位\n",
    "    # 那么二进制位的下标范围为 [0, 17]\n",
    "    MAXD = 17\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "\n",
    "        # 将 parents 存储为树的形式，方便进行深度优先遍历\n",
    "        edges = defaultdict(list)\n",
    "        # 找出根节点\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "\n",
    "        q = len(queries)\n",
    "        # 使用离线的思想，stored[i] 存储了所有节点 i 对应的询问\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "\n",
    "        r = Trie()\n",
    "\n",
    "        # 向字典树添加一个数\n",
    "        def trie_insert(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                cur.cnt += 1\n",
    "\n",
    "        # 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值\n",
    "        def trie_query(x: int) -> int:\n",
    "            cur, ret = r, 0\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                else:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return ret\n",
    "\n",
    "        # 从字典树中删除一个数\n",
    "        def trie_erase(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1\n",
    "\n",
    "        # 深度优先遍历\n",
    "        def dfs(u: int) -> None:\n",
    "            trie_insert(u)\n",
    "            for idx, num in stored[u]:\n",
    "                ans[idx] = trie_query(num)\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            trie_erase(u)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    # 由于我们的字典树需要支持删除数的操作\n",
    "    # 因此这里使用 cnt 变量进行记录该节点对应的数的个数\n",
    "    cnt: int = 0\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # 最大的数的二进制表示不会超过 18 位\n",
    "    # 那么二进制位的下标范围为 [0, 17]\n",
    "    MAXD = 17\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "\n",
    "        # 将 parents 存储为树的形式，方便进行深度优先遍历\n",
    "        edges = defaultdict(list)\n",
    "        # 找出根节点\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "\n",
    "        q = len(queries)\n",
    "        # 使用离线的思想，stored[i] 存储了所有节点 i 对应的询问\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "\n",
    "        r = Trie()\n",
    "\n",
    "        # 向字典树添加一个数\n",
    "        def trie_insert(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                cur.cnt += 1\n",
    "\n",
    "        # 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值\n",
    "        def trie_query(x: int) -> int:\n",
    "            cur, ret = r, 0\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                else:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return ret\n",
    "\n",
    "        # 从字典树中删除一个数\n",
    "        def trie_erase(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1\n",
    "\n",
    "        # 深度优先遍历\n",
    "        def dfs(u: int) -> None:\n",
    "            trie_insert(u)\n",
    "            for idx, num in stored[u]:\n",
    "                ans[idx] = trie_query(num)\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            trie_erase(u)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 离线算法 + 字典树\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    # 由于我们的字典树需要支持删除数的操作\n",
    "    # 因此这里使用 cnt 变量进行记录该节点对应的数的个数\n",
    "    cnt: int = 0\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # 最大的数的二进制表示不会超过 18 位\n",
    "    # 那么二进制位的下标范围为 [0, 17]\n",
    "    MAXD = 17\n",
    "\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "\n",
    "        # 将 parents 存储为树的形式，方便进行深度优先遍历\n",
    "        edges = defaultdict(list)\n",
    "        # 找出根节点\n",
    "        root = -1\n",
    "        for i, parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "\n",
    "        q = len(queries)\n",
    "        # 使用离线的思想，stored[i] 存储了所有节点 i 对应的询问\n",
    "        stored = defaultdict(list)\n",
    "        ans = [0] * q\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            stored[node].append((i, val))\n",
    "\n",
    "        r = Trie()\n",
    "\n",
    "        # 向字典树添加一个数\n",
    "        def trie_insert(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                cur.cnt += 1\n",
    "\n",
    "        # 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值\n",
    "        def trie_query(x: int) -> int:\n",
    "            cur, ret = r, 0\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                else:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        ret |= (1 << i)\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return ret\n",
    "\n",
    "        # 从字典树中删除一个数\n",
    "        def trie_erase(x: int) -> None:\n",
    "            cur = r\n",
    "            for i in range(Solution.MAXD, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1\n",
    "\n",
    "        # 深度优先遍历\n",
    "        def dfs(u: int) -> None:\n",
    "            trie_insert(u)\n",
    "            for idx, num in stored[u]:\n",
    "                ans[idx] = trie_query(num)\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "            trie_erase(u)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.cnt = 0\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        root = TrieNode()\n",
    "        start = 0\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if parents[i] == - 1:\n",
    "                start = i\n",
    "                continue \n",
    "            graph[parents[i]].append(i)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for idx, q in enumerate(queries):\n",
    "            dic[q[0]].append([idx, q[1]])\n",
    "        def addNode(val):\n",
    "            node = root \n",
    "            for i in range(32, - 1, - 1):\n",
    "                bit = (val >> i) & 1 \n",
    "                if bit not in node.children:\n",
    "                    node.children[bit] = TrieNode()\n",
    "                node = node.children[bit]\n",
    "                node.cnt += 1 \n",
    "        \n",
    "        def deleteNode(val):\n",
    "            node = root \n",
    "            for i in range(32, - 1, - 1):\n",
    "                bit = (val >> i) & 1 \n",
    "                node = node.children[bit]\n",
    "                node.cnt -= 1 \n",
    "        \n",
    "        def getVal(val):\n",
    "            node = root \n",
    "            XOR = 0\n",
    "            for i in range(32, - 1, - 1):\n",
    "                bit = (val >> i) & 1 \n",
    "                if bit ^ 1 in node.children and node.children[bit ^ 1].cnt > 0:\n",
    "                    XOR |= 1 << i \n",
    "                    node = node.children[bit ^ 1]\n",
    "                elif bit in node.children and node.children[bit].cnt > 0:\n",
    "                    node = node.children[bit]\n",
    "                else:\n",
    "                    return 0\n",
    "            return XOR \n",
    "        res = [0] * len(queries)\n",
    "        def dfs(node, par):\n",
    "            addNode(node)\n",
    "            for idx, val in dic[node]:\n",
    "                res[idx] = getVal(val)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                dfs(nei, node)\n",
    "            deleteNode(node)\n",
    "        dfs(start, - 1)\n",
    "        return res \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.cnt = 0\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        root = TrieNode()\n",
    "        start = 0\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if parents[i] == - 1:\n",
    "                start = i\n",
    "                continue \n",
    "            graph[parents[i]].append(i)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for idx, q in enumerate(queries):\n",
    "            dic[q[0]].append([idx, q[1]])\n",
    "        def addNode(val):\n",
    "            node = root \n",
    "            for i in range(32, - 1, - 1):\n",
    "                bit = (val >> i) & 1 \n",
    "                if bit not in node.children:\n",
    "                    node.children[bit] = TrieNode()\n",
    "                node = node.children[bit]\n",
    "                node.cnt += 1 \n",
    "        \n",
    "        def deleteNode(val):\n",
    "            node = root \n",
    "            for i in range(32, - 1, - 1):\n",
    "                bit = (val >> i) & 1 \n",
    "                node = node.children[bit]\n",
    "                node.cnt -= 1 \n",
    "        \n",
    "        def getVal(val):\n",
    "            node = root \n",
    "            XOR = 0\n",
    "            for i in range(32, - 1, - 1):\n",
    "                bit = (val >> i) & 1 \n",
    "                if bit ^ 1 in node.children and node.children[bit ^ 1].cnt > 0:\n",
    "                    XOR |= 1 << i \n",
    "                    node = node.children[bit ^ 1]\n",
    "                elif bit in node.children and node.children[bit].cnt > 0:\n",
    "                    node = node.children[bit]\n",
    "                else:\n",
    "                    return 0\n",
    "            return XOR \n",
    "        res = [0] * len(queries)\n",
    "        def dfs(node, par):\n",
    "            addNode(node)\n",
    "            for idx, val in dic[node]:\n",
    "                res[idx] = getVal(val)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                dfs(nei, node)\n",
    "            deleteNode(node)\n",
    "        dfs(start, - 1)\n",
    "        return res \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left = None\n",
    "    right = None\n",
    "    cnt = 0    \n",
    "class Solution:\n",
    "    MAXD = 17\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        r = Trie()\n",
    "        def trie_insert(x):\n",
    "            cur = r \n",
    "            for i in range(Solution.MAXD,-1,-1):\n",
    "                if x & (1 << i):\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                cur.cnt += 1\n",
    "        def trie_delete(x):\n",
    "            cur = r \n",
    "            for i in range(Solution.MAXD,-1,-1):\n",
    "                if x & (1 << i):\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                cur.cnt -= 1\n",
    "        def trie_query(x):\n",
    "            cur = r \n",
    "            res = 0\n",
    "            for i in range(Solution.MAXD,-1,-1):\n",
    "                if x & (1 << i):\n",
    "                    if cur.left and cur.left.cnt:\n",
    "                        res |= (1 << i)\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                else:\n",
    "                    if cur.right and cur.right.cnt:\n",
    "                        res |= (1 << i)\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "            return res\n",
    "        edges = defaultdict(list)\n",
    "        root = -1\n",
    "        for i,parent in enumerate(parents):\n",
    "            if parent == -1:\n",
    "                root = i \n",
    "            else:\n",
    "                edges[parent].append(i)\n",
    "        stored = defaultdict(list)\n",
    "        for i,(node,val) in enumerate(queries):\n",
    "            stored[node].append((i,val))\n",
    "        ans = [0]*len(queries)\n",
    "        def dfs(x):\n",
    "            trie_insert(x)\n",
    "            for idx,val in stored[x]:\n",
    "                ans[idx] = trie_query(val)\n",
    "            for i in edges[x]:\n",
    "                dfs(i)\n",
    "            trie_delete(x)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = [0, 0]\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    def insert(self, x):\n",
    "        cur = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (x >> i) & 1\n",
    "            cur.cnt[bit] += 1\n",
    "            if not cur.children[bit]:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "    def query(self, x):\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (x >> i) & 1\n",
    "            flip_bit = 1 - bit\n",
    "            #想要找xor的最大值 优先去flip_bit\n",
    "            if cur.children[flip_bit]:\n",
    "                ans |= 1 << i\n",
    "                cur = cur.children[flip_bit]\n",
    "            else:\n",
    "                cur = cur.children[bit]\n",
    "\n",
    "        return ans\n",
    "    \n",
    "    def remove(self, x):\n",
    "        cur = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (x >> i) & 1\n",
    "            cur.cnt[bit] -= 1\n",
    "            nxt = cur.children[bit]\n",
    "            if cur.cnt[bit] == 0:\n",
    "                cur.children[bit] = None\n",
    "            cur = nxt\n",
    "        \n",
    "    \n",
    "class Solution:\n",
    "    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q = defaultdict(list)\n",
    "        for i, (node, val) in enumerate(queries):\n",
    "            q[node].append((val, i))\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        root = None\n",
    "        for x, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                root = x\n",
    "                continue\n",
    "            g[x].append(p)\n",
    "            g[p].append(x)\n",
    "        trie = Trie()\n",
    "        ans = [0] * len(queries)\n",
    "        def dfs(x, fa):\n",
    "            trie.insert(x)\n",
    "            for val, idx in q[x]:\n",
    "                ans[idx] = trie.query(val)\n",
    "            for y in g[x]:\n",
    "                if fa != y:\n",
    "                    dfs(y, x)\n",
    "            trie.remove(x)\n",
    "        dfs(root, -1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
